public class Solution5 {
    public int waysToStep(int n) {
        int MOD = (int)1e9 +7;
        //处理边界情况
        if(n==1||n==2) return n;
        if(n==3) return 4;
        //1.创建dp表
        int[] dp = new int[n+1];

        //2.初始化
        dp[1] = 1;dp[2] = 2;dp[3] = 4;
        //3.填表
        for(int i=4;i<=n;i++) {
            dp[i] = ((dp[i-1] + dp[i-2])%MOD + dp[i-3])%MOD;
        }
        //4.返回值
        return dp[n];
    }
}
